#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_set>
#include <string>
#include <climits>
#include <algorithm>
using namespace std;

class Graph
{
private:
    vector<vector<int>> adjacencyMatrix;
    vector<int> nodeValues;
    int numEdges;

public:
    Graph(int nodes)
    {
        adjacencyMatrix.resize(nodes, vector<int>(nodes, 0));
        nodeValues.resize(nodes, 0);
        numEdges = 0;
    }

    void addEdge(int u, int v)
    {
        adjacencyMatrix[u][v] = 1;
        adjacencyMatrix[v][u] = 1;
        ++numEdges;
    }

    void setNodeValue(int node, int value)
    {
        nodeValues[node] = value;
    }   

    void displayAdjacencyMatrix()
    {
        cout << "邻接矩阵：" << endl;
        for (const auto &row : adjacencyMatrix)
        {
            for (int val : row)
            {
                cout << val << " ";
            }
            cout << endl;
        }
    }

    void bfsSearch(int startNode, int targetNode)
    {
        cout << "搜索#" << char(startNode + 'A') << "->" << char(targetNode + 'A') << "  :";
        vector<bool> visited(adjacencyMatrix.size(), false);
        queue<int> q;
        q.push(startNode);
        visited[startNode] = true;

        while (!q.empty())
        {
            int node = q.front();
            q.pop();
            cout << char('A' + node)<<":"<<node << " ";

            if (node == targetNode)
            {
                break;
            }

            for (int i = 0; i < adjacencyMatrix[node].size(); ++i)
            {
                if (adjacencyMatrix[node][i] == 1 && !visited[i])
                {
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
        cout << endl;
    }

    void bfsTraversal()
    {
        vector<bool> visited(adjacencyMatrix.size(), false);
        queue<int> q;

        for (int i = 0; i < adjacencyMatrix.size(); ++i)
        {
            if (!visited[i])
            {
                q.push(i);
                visited[i] = true;

                while (!q.empty())
                {
                    int node = q.front();
                    q.pop();
                    cout << char('A' + node) << ":" << node << " ";

                    for (int j = 0; j < adjacencyMatrix[node].size(); ++j)
                    {
                        if (adjacencyMatrix[node][j] == 1 && !visited[j])
                        {
                            q.push(j);
                            visited[j] = true;
                        }
                    }
                }
            }
        }
        cout << endl;
    }

    void dfsSearch(int startNode, int targetNode)
    {
        cout << "搜索#" << char(startNode + 'A') << "->" << char(targetNode + 'A') << "  :";
        vector<bool> visited(adjacencyMatrix.size(), false);
        stack<int> s;
        s.push(startNode);
        visited[startNode] = true;

        while (!s.empty())
        {
            int node = s.top();
            s.pop();
            cout << char('A' + node) << ":" << node << " ";

            if (node == targetNode)
            {
                break;
            }

            for (int i = 0; i < adjacencyMatrix[node].size(); ++i)
            {
                if (adjacencyMatrix[node][i] == 1 && !visited[i])
                {
                    s.push(i);
                    visited[i] = true;
                }
            }
        }
        cout << endl;
    }

    void dfsTraversal()
    {
        vector<bool> visited(adjacencyMatrix.size(), false);
        stack<int> s;

        for (int i = 0; i < adjacencyMatrix.size(); ++i)
        {
            if (!visited[i])
            {
                s.push(i);
                visited[i] = true;

                while (!s.empty())
                {
                    int node = s.top();
                    s.pop();
                    cout << char('A' + node) << ":" << node << " ";

                    for (int j = 0; j < adjacencyMatrix[node].size(); ++j)
                    {
                        if (adjacencyMatrix[node][j] == 1 && !visited[j])
                        {
                            s.push(j);
                            visited[j] = true;
                        }
                    }
                }
            }
        }
        cout << endl;
    }

    void displayAllPaths(int startNode, int endNode)
    {
        vector<int> path;
        unordered_set<string> paths;
        int minEdges = INT_MAX;
        int maxEdges = INT_MIN;
        dfsAllPaths(startNode, endNode, path, paths, minEdges, maxEdges);

        cout << "所有路径：" << endl;
        for (const string &edgePath : paths)
        {
            cout << edgePath << endl;
        }
        cout << "边最长路径: " << maxEdges << endl;
        cout << "边最短路径: " << minEdges << endl;
    }

    void dfsTraversal(int startNode)
    {
        vector<bool> visited(adjacencyMatrix.size(), false);
        stack<int> s;
        s.push(startNode);
        visited[startNode] = true;

        cout << "DFS遍历结果：" << endl;

        while (!s.empty())
        {
            int node = s.top();
            s.pop();
            cout << char('A' + node) << " ";

            for (int i = adjacencyMatrix[node].size() - 1; i >= 0; --i)
            {
                if (adjacencyMatrix[node][i] == 1 && !visited[i])
                {
                    s.push(i);
                    visited[i] = true;
                }
            }
        }
        cout << endl;
    }

private:
    void dfsAllPaths(int startNode, int endNode, vector<int> &path, unordered_set<string> &paths, int &minEdges, int &maxEdges)
    {
        path.push_back(startNode);

        if (startNode == endNode)
        {
            string edgePath;
            int edgeCount = path.size() - 1;
            for (int i = 0; i < path.size() - 1; ++i)
            {
                edgePath += "(" + string(1, char('A' + path[i])) + ", " + string(1, char('A' + path[i + 1])) + ") ";
            }
            paths.insert(edgePath);
            minEdges = min(minEdges, edgeCount);
            maxEdges = max(maxEdges, edgeCount);
        }
        else
        {
            for (int i = 0; i < adjacencyMatrix[startNode].size(); ++i)
            {
                if (adjacencyMatrix[startNode][i] == 1 && find(path.begin(), path.end(), i) == path.end())
                {
                    dfsAllPaths(i, endNode, path, paths, minEdges, maxEdges);
                }
            }
        }

        path.pop_back();
    }
};

int main()
{
    Graph g(7); // 创建一个有7个节点的图

    g.addEdge(0, 5);
    g.addEdge(0, 6);
    g.addEdge(1, 6);
    g.addEdge(1, 2);
    g.addEdge(2, 4);
    g.addEdge(4, 3);
    g.addEdge(4, 5);
    g.addEdge(3, 6);

    g.setNodeValue(0, 0);
    g.setNodeValue(1, 1);
    g.setNodeValue(2, 2);
    g.setNodeValue(3, 3);
    g.setNodeValue(4, 4);
    g.setNodeValue(5, 5);
    g.setNodeValue(6, 6);

    g.displayAdjacencyMatrix();

    cout << endl
         << "广度优先搜索结果：" << endl;
    g.bfsSearch(0, 3);

    cout << endl
         << "广度优先遍历结果：" << endl;
    g.bfsTraversal();

    cout << endl
         << "深度优先搜索结果：" << endl;
    g.dfsSearch(0, 3);

    g.dfsTraversal(0);

    g.displayAllPaths(0, 3);
    return 0;
}